package com.fulin.leetcode;

/**
 * 合并升序链表
 *
 * @Author fulin
 * @Date 2022/9/14 14:43
 **/
public class Num23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode node = null;
        for(int i = 0;i < lists.length;i++){
            node = merge(node,lists[i]);
        }
        return node;
    }

    private static ListNode merge(ListNode left,ListNode right){
        if(left == null || right == null){
            return left == null ? right : left;
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy,aPat = left,bPat = right;
        while(aPat != null && bPat != null){
            if(aPat.val > bPat.val){
                tail.next = bPat;
                bPat = bPat.next;
            }else{
                tail.next = aPat;
                aPat = aPat.next;
            }
            tail = tail.next;
        }
        tail.next = aPat != null ? aPat : bPat;
        return dummy.next;
    }
}
